#include<bits/stdc++.h>
using namespace std;

//Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct retType {
    bool isBT;
    int treeHeight;
    retType(bool isBT,int treeHeight) {
        this->isBT = isBT;
        this->treeHeight = treeHeight;
    }
};
retType isBalance2(TreeNode* head) {
    if (!head) return retType(true, 0);
    retType  left = isBalance2(head->left);
    retType right = isBalance2(head->right);
    int dis = abs(left.treeHeight - right.treeHeight);
    if ((left.isBT && right.isBT) && dis < 2) {
        return { true,max(left.treeHeight,right.treeHeight) + 1 };
    }
    else return{ false,max(left.treeHeight,right.treeHeight) + 1 };
}
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        retType ret = isBalance2(root);
        if (ret.isBT) return true;
        else return false;
    }
};